{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #最小路径和"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #dynamic-programming #matrix"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #动态规划 #矩阵"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: minPathSum"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #最小路径和"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个包含非负整数的 <code><em>m</em>&nbsp;x&nbsp;<em>n</em></code>&nbsp;网格&nbsp;<code>grid</code> ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。</p>\n",
    "\n",
    "<p><strong>说明：</strong>一个机器人每次只能向下或者向右移动一步。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2020/11/05/minpath.jpg\" style=\"width: 242px; height: 242px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>grid = [[1,3,1],[1,5,1],[4,2,1]]\n",
    "<strong>输出：</strong>7\n",
    "<strong>解释：</strong>因为路径 1&rarr;3&rarr;1&rarr;1&rarr;1 的总和最小。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>grid = [[1,2,3],[4,5,6]]\n",
    "<strong>输出：</strong>12\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>m == grid.length</code></li>\n",
    "\t<li><code>n == grid[i].length</code></li>\n",
    "\t<li><code>1 &lt;= m, n &lt;= 200</code></li>\n",
    "\t<li><code>0 &lt;= grid[i][j] &lt;= 100</code></li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><meta charset=\"UTF-8\" />注意：本题与主站 64&nbsp;题相同：&nbsp;<a href=\"https://leetcode-cn.com/problems/minimum-path-sum/\">https://leetcode-cn.com/problems/minimum-path-sum/</a></p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [0i0mDW](https://leetcode.cn/problems/0i0mDW/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [0i0mDW](https://leetcode.cn/problems/0i0mDW/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[1,3,1],[1,5,1],[4,2,1]]', '[[1,2,3],[4,5,6]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minPathSum(self, grid: List[List[int]]) -> int:\n",
    "        dp, dp[0], length, width = [0] *len(grid[0]), grid[0][0], len(grid[0]), len(grid)\n",
    "        \n",
    "        for i in range(1, length):\n",
    "            dp[i] = dp[i -1] +grid[0][i]\n",
    "        \n",
    "        for i in range(1, width):\n",
    "            for j in range(length):\n",
    "                dp[j] = dp[j] +grid[i][j] if j == 0 else grid[i][j] +min(dp[j -1], dp[j])\n",
    "                \n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minPathSum(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        dp = [100000000 for _ in range(n+1)]\n",
    "        dp[1] = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                dp[j+1] = min(dp[j], dp[j+1]) + grid[i][j]\n",
    "        return dp[-1]\n",
    "\n",
    "        # for i in range(m):\n",
    "        #     for j in range(n):\n",
    "        #         if i == 0 and j == 0:\n",
    "        #             continue\n",
    "        #         if i == 0:\n",
    "        #             grid[i][j] += grid[i][j-1]\n",
    "        #         elif j == 0:\n",
    "        #             grid[i][j] += grid[i-1][j]\n",
    "        #         else:\n",
    "        #             grid[i][j] += min(grid[i][j-1], grid[i-1][j])\n",
    "        # return grid[-1][-1]\n",
    "\n",
    "\n",
    "\n",
    "                \n",
    "\n",
    "        # for i in range(m-1, -1, -1):\n",
    "        #     for j in range(n-1, -1, -1):\n",
    "        #         if i == 0 and j == 0:\n",
    "        #             return grid[i][j]\n",
    "        #         if i == 0:\n",
    "        #             grid[i][j-1] += grid[i][j]\n",
    "        #         elif j == 0:\n",
    "        #             grid[i-1][j] += grid[i][j]\n",
    "        #         else:\n",
    "        #             if grid"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minPathSum(self, grid: List[List[int]]) -> int:\n",
    "        dp, dp[0], length, width = [0] *len(grid[0]), grid[0][0], len(grid[0]), len(grid)\n",
    "        \n",
    "        for i in range(1, length):\n",
    "            dp[i] = dp[i -1] +grid[0][i]\n",
    "        \n",
    "        for i in range(1, width):\n",
    "            for j in range(length):\n",
    "                dp[j] = dp[j] +grid[i][j] if j == 0 else grid[i][j] +min(dp[j -1], dp[j])\n",
    "                \n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minPathSum(self, grid: List[List[int]]) -> int:\n",
    "        if not grid:\n",
    "            return 0\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        dp = [[0] * n] * m\n",
    "        dp[0][0] = grid[0][0]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if i - 1 >= 0 and j - 1 >= 0:\n",
    "                    dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]\n",
    "                elif i - 1 >= 0 and j - 1 < 0:\n",
    "                    dp[i][j] = dp[i-1][j] + grid[i][j]\n",
    "                elif j - 1 >= 0 and i - 1 < 0:\n",
    "                    dp[i][j] = dp[i][j-1] + grid[i][j]\n",
    "        return dp[m-1][n-1]\n",
    "\n",
    "\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minPathSum(self, grid: List[List[int]]) -> int:\n",
    "        dp, dp[0], length, width = [0] *len(grid[0]), grid[0][0], len(grid[0]), len(grid)\n",
    "        \n",
    "        for i in range(1, length):\n",
    "            dp[i] = dp[i -1] +grid[0][i]\n",
    "        \n",
    "        for i in range(1, width):\n",
    "            for j in range(length):\n",
    "                dp[j] = dp[j] +grid[i][j] if j == 0 else grid[i][j] +min(dp[j -1], dp[j])\n",
    "                \n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minPathSum(self, grid: List[List[int]]) -> int:\n",
    "            m,n=len(grid),len(grid[0])\n",
    "            dp=[0]*n\n",
    "            for i in range(m):\n",
    "                for j in range(n):\n",
    "                    if i==0:\n",
    "                        if j==0:\n",
    "                            dp[j]=grid[i][j]\n",
    "                        else:\n",
    "                            dp[j]=dp[j-1]+grid[i][j]\n",
    "                    elif j==0:\n",
    "                        dp[j]+=grid[i][j]\n",
    "                    else:\n",
    "                        dp[j]=min(dp[j-1]+grid[i][j],dp[j]+grid[i][j])\n",
    "            return dp[n-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minPathSum(self, grid: List[List[int]]) -> int:\n",
    "        dp, dp[0], length, width = [0] *len(grid[0]), grid[0][0], len(grid[0]), len(grid)\n",
    "        \n",
    "        for i in range(1, length):\n",
    "            dp[i] = dp[i -1] +grid[0][i]\n",
    "        \n",
    "        for i in range(1, width):\n",
    "            for j in range(length):\n",
    "                dp[j] = dp[j] +grid[i][j] if j == 0 else grid[i][j] +min(dp[j -1], dp[j])\n",
    "                \n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minPathSum(self, grid: List[List[int]]) -> int:\n",
    "        matrix = [float('inf') for i in range(len(grid[0]))]\n",
    "        matrix[0] = 0\n",
    "        for row in range(len(grid)):\n",
    "            matrix[0] += grid[row][0]\n",
    "            for col in range(1, len(grid[0])):\n",
    "                matrix[col] = min(matrix[col], matrix[col-1]) + grid[row][col]\n",
    "        return matrix[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minPathSum(self, grid: List[List[int]]) -> int:\n",
    "        n, m = len(grid), len(grid[0])\n",
    "        cur = list(accumulate(grid[0]))\n",
    "        for i in range(1, n):\n",
    "            for j in range(m):\n",
    "                if j == 0:\n",
    "                    cur[j] += grid[i][j]\n",
    "                else:\n",
    "                    cur[j] = min(cur[j] + grid[i][j], cur[j - 1] + grid[i][j])\n",
    "        return cur[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minPathSum(self, grid: List[List[int]]) -> int:\n",
    "        m,n=len(grid),len(grid[0])\n",
    "        dp=grid[0].copy()\n",
    "        for j in range(1,n):dp[j]+=dp[j-1]\n",
    "        for i in range(1,m):\n",
    "            for j in range(n):\n",
    "                if j ==0 :\n",
    "                    dp[j]+=grid[i][j]\n",
    "                else:\n",
    "                    dp[j]=min(dp[j],dp[j-1])+grid[i][j]\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minPathSum(self, grid: List[List[int]]) -> int:\n",
    "        m,n = len(grid), len(grid[0])\n",
    "\n",
    "        dp = [0 for _ in range(n)]\n",
    "        dp[0] = grid[0][0]\n",
    "        for i in range(1, n):\n",
    "            dp[i] = dp[i-1] + grid[0][i]\n",
    "\n",
    "        for i in range(1, m):\n",
    "            dp[0] = dp[0] + grid[i][0]\n",
    "            for j in range(1, n):\n",
    "                dp[j] = min(dp[j-1], dp[j]) + grid[i][j]\n",
    "        \n",
    "        return dp[n-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minPathSum(self, grid: List[List[int]]) -> int:\n",
    "        #优化解法1的空间复杂度 变成一维数组\n",
    "        rows = len(grid)\n",
    "        cols = len(grid[0])\n",
    "        dp=[]\n",
    "        for j in range(cols):\n",
    "            if j > 0 :\n",
    "                dp.append(grid[0][j]+dp[j-1])\n",
    "            else:\n",
    "                dp.append(grid[0][j])\n",
    "        for i in range(1,rows):\n",
    "            for j in range(cols):\n",
    "                if j==0:\n",
    "                    tmp=dp[j]\n",
    "                else:\n",
    "                    tmp= min(dp[j - 1], dp[j])\n",
    "                dp[j]=tmp + grid[i][j]\n",
    "        # print(dp)\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minPathSum(self, grid: List[List[int]]) -> int:\n",
    "        if len(grid) == 1:\n",
    "            return sum(grid[0])\n",
    "        if len(grid[0]) == 1:\n",
    "            return sum([x[0] for x in grid])\n",
    "        \n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        dp = [0] * n\n",
    "        dp[0] = grid[0][0]\n",
    "        for j in range(1, n):\n",
    "            dp[j] = dp[j-1] + grid[0][j]\n",
    "        \n",
    "        for i in range(1, m):\n",
    "            dp[0] = dp[0] + grid[i][0]\n",
    "            for j in range(1, n):\n",
    "                dp[j] = min(dp[j], dp[j-1]) + grid[i][j]\n",
    "        \n",
    "        return dp[n-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minPathSum(self, grid: List[List[int]]) -> int:\n",
    "        dp=[]\n",
    "        for i in grid[0]:\n",
    "            if dp:\n",
    "                dp.append(dp[-1]+i)\n",
    "            else:\n",
    "                dp.append(i)\n",
    "        for i in range(1,len(grid)):\n",
    "            t=[]\n",
    "            for j in range(len(grid[0])):\n",
    "                if not t:\n",
    "                    t.append(dp[j]+grid[i][j])\n",
    "                else:\n",
    "                    t.append(min(dp[j],t[-1])+grid[i][j])\n",
    "            dp=t\n",
    "        return dp[-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minPathSum(self, grid: List[List[int]]) -> int:\n",
    "        dp = [0 for i in range(len(grid[0]))]\n",
    "        for i in range(len(grid)):\n",
    "            for j in range(len(grid[0])):\n",
    "                if i==0 and j==0:\n",
    "                    dp[j] = grid[0][0]\n",
    "                    continue\n",
    "                if i==0:\n",
    "                    dp[j] = dp[j-1] + grid[i][j]\n",
    "                    continue\n",
    "                if j==0:\n",
    "                    dp[j] = dp[j] + grid[i][j]\n",
    "                    continue\n",
    "                else:\n",
    "                    dp[j] = min(dp[j-1]+grid[i][j], dp[j]+grid[i][j])\n",
    "        return dp[-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minPathSum(self, grid: List[List[int]]) -> int:\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        dp = [0 for _ in range(n)]\n",
    "        dp[0] = grid[0][0]\n",
    "        for i in range(1,n):\n",
    "            dp[i] = dp[i-1] + grid[0][i]\n",
    "\n",
    "        for row in range(1, m):\n",
    "            dp[0] += grid[row][0]\n",
    "            for col in range(1, n):\n",
    "                dp[col] = min( dp[col-1], dp[col] ) + grid[row][col]\n",
    "            print(dp)\n",
    "\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minPathSum(self, grid: List[List[int]]) -> int:\n",
    "        dp = [0 for i in range(len(grid[0]))]\n",
    "        for i in range(len(grid)):\n",
    "            for j in range(len(grid[0])):\n",
    "                if i==0 and j==0:\n",
    "                    dp[j] = grid[0][0]\n",
    "                    continue\n",
    "                if i==0:\n",
    "                    dp[j] = dp[j-1] + grid[i][j]\n",
    "                    continue\n",
    "                if j==0:\n",
    "                    dp[j] = dp[j] + grid[i][j]\n",
    "                    continue\n",
    "                else:\n",
    "                    dp[j] = min(dp[j-1]+grid[i][j], dp[j]+grid[i][j])\n",
    "        return dp[-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minPathSum(self, grid: List[List[int]]) -> int:\n",
    "        m=len(grid)\n",
    "        n=len(grid[0])\n",
    "        dp=[[0 for _ in range(n)]for _ in range(m)]\n",
    "        dp[0][0]=grid[0][0]\n",
    "        for i in range(1,m):\n",
    "            dp[i][0]=dp[i-1][0]+grid[i][0]\n",
    "        for j in range(1,n):\n",
    "            dp[0][j]=dp[0][j-1]+grid[0][j]\n",
    "        for i in range(1,m):\n",
    "            for j in range(1,n):\n",
    "                dp[i][j]=min(dp[i-1][j],dp[i][j-1])+grid[i][j]\n",
    "        return dp[-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minPathSum(self, grid: List[List[int]]) -> int:\n",
    "        if not grid or not grid[0]:\n",
    "            return 0\n",
    "        \n",
    "        rows, columns = len(grid), len(grid[0])\n",
    "        dp = [[0] * columns for _ in range(rows)]\n",
    "        dp[0][0] = grid[0][0]\n",
    "        for i in range(1, rows):\n",
    "            dp[i][0] = dp[i - 1][0] + grid[i][0]\n",
    "        for j in range(1, columns):\n",
    "            dp[0][j] = dp[0][j - 1] + grid[0][j]\n",
    "        for i in range(1, rows):\n",
    "            for j in range(1, columns):\n",
    "                dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j]\n",
    "        \n",
    "        return dp[rows - 1][columns - 1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minPathSum(self, grid: List[List[int]]) -> int:\n",
    "        n, m = len(grid), len(grid[0])\n",
    "        f = [[inf] * (m + 1) for i in range(2)]\n",
    "\n",
    "        # f[i][j] = min(f[i - 1][j], f[i][j - 1]) + grid[i][j]\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                mn = min(f[i % 2][j + 1], f[(i + 1) % 2][j])\n",
    "                f[(i + 1) % 2][j + 1] = (mn if mn != inf else 0) + grid[i][j]\n",
    "            print(f[(i + 1) % 2])\n",
    "        return f[n % 2][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minPathSum(self, grid: List[List[int]]) -> int:\n",
    "        m,n = len(grid),len(grid[0])\n",
    "        dp = [[0]*n for _ in range(m)]\n",
    "        dp[0][0] = grid[0][0]\n",
    "        for i in range(1,m):\n",
    "            dp[i][0] = dp[i-1][0] + grid[i][0]\n",
    "        for j in range(1,n):\n",
    "            dp[0][j] = dp[0][j-1] + grid[0][j]\n",
    "        for i in range(1,m):\n",
    "            for j in range(1,n):\n",
    "                dp[i][j] = min(dp[i-1][j],dp[i][j-1]) + grid[i][j]\n",
    "        return dp[-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minPathSum(self, grid: List[List[int]]) -> int:\n",
    "        #动态规划  空间换时间\n",
    "        m, n = len(grid),len(grid[0])\n",
    "        dp = [[0 for i in range (n)] for j in range(m)]\n",
    "        dp[0][0] = grid[0][0]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if i == 0 and j >0:\n",
    "                    dp[i][j] = dp[i][j-1] + grid[i][j]\n",
    "                elif j == 0 and i >0:\n",
    "                    dp[i][j] = dp[i-1][j] + grid[i][j]\n",
    "                elif j > 0 and i > 0 :\n",
    "                    dp[i][j] = min(dp[i-1][j],dp[i][j-1]) + grid[i][j]\n",
    "        return dp[m-1][n-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def minPathSum(self, grid: List[List[int]]) -> int:\n",
    "#         n = len(grid)\n",
    "#         m = len(grid[0])\n",
    "#         dp = [[0]* m for _ in range(n)]\n",
    "#         dp[0][0] = grid[0][0]\n",
    "#         for i in range(1, n):\n",
    "#             dp[i][0] = dp[i-1][0] + grid[i][0]\n",
    "#         for j in range(1, n):\n",
    "#             dp[0][j] = dp[0][j-1] + grid[0][j]\n",
    "#         for i in range(1,n):\n",
    "#             for j in range(1, m):\n",
    "#                 dp[i][j] = min(dp[i-1][j], dp[i][j-1])+ grid[i][j]\n",
    "#         return dp[n-1][m-1]\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def minPathSum(self, grid: List[List[int]]) -> int:\n",
    "        n = len(grid)\n",
    "        m = len(grid[0])\n",
    "        dp = [[0] * m for _ in range(n)]\n",
    "        dp[0][0] = grid[0][0]\n",
    "\n",
    "        for i in range(1, n):\n",
    "            dp[i][0] = dp[i-1][0] + grid[i][0]\n",
    "        for j in range(1, m):\n",
    "            dp[0][j] = dp[0][j-1] + grid[0][j]\n",
    "        for i in range(1, n):\n",
    "            for j in range(1, m):\n",
    "                dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]\n",
    "\n",
    "        return dp[n-1][m-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minPathSum(self, grid: List[List[int]]) -> int:\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "\n",
    "        dp = [[0] * n for _ in range(m)]\n",
    "        dp[0][0] = grid[0][0]\n",
    "        for i in range(1, m):\n",
    "            dp[i][0] = dp[i - 1][0] + grid[i][0]\n",
    "        \n",
    "        for j in range(1, n):\n",
    "            dp[0][j] = dp[0][j - 1] + grid[0][j]\n",
    "        \n",
    "        for i in range(1, m):\n",
    "            for j in range(1, n):\n",
    "                dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j]\n",
    "        \n",
    "        return dp[-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minPathSum(self, grid: List[List[int]]) -> int:\n",
    "        m,n=len(grid),len(grid[0])\n",
    "        dp=[[0]*n for _ in range(m)]\n",
    "\n",
    "        dp[0][0]=grid[0][0]\n",
    "        for i in range(1,m):\n",
    "            dp[i][0]=dp[i-1][0]+grid[i][0]\n",
    "        for j in range(1,n):\n",
    "            dp[0][j]=dp[0][j-1]+grid[0][j]\n",
    "        for i in range(1,m):\n",
    "            for j in range(1,n):\n",
    "                dp[i][j]=min(dp[i-1][j],dp[i][j-1])+grid[i][j]\n",
    "        return dp[m-1][n-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.memo = []\n",
    "\n",
    "    def minPathSum(self, grid: List[List[int]]) -> int:\n",
    "        self.memo = [[-1] * len(grid[0]) for _ in range(len(grid))]\n",
    "        return self.dp(grid, 0, 0)\n",
    "\n",
    "    def dp(self, grid, row, col):\n",
    "        if row == (len(grid) - 1) and col == (len(grid[0]) - 1):\n",
    "            self.memo[row][col] = grid[row][col]\n",
    "            return self.memo[row][col]\n",
    "        if row >= len(grid) or col >= len(grid[0]):\n",
    "            return float('inf')\n",
    "\n",
    "        if self.memo[row][col] != -1:\n",
    "            return self.memo[row][col]\n",
    "\n",
    "        self.memo[row][col] = min(\n",
    "            self.dp(grid, row + 1, col),\n",
    "            self.dp(grid, row, col + 1)\n",
    "        ) + grid[row][col]\n",
    "\n",
    "        return self.memo[row][col]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minPathSum(self, grid: List[List[int]]) -> int:\n",
    "        m,n =len(grid),len(grid[0])\n",
    "        save = [[-1]*n for i in range(m)]\n",
    "        def dfs(i,j):\n",
    "            if i==0 and j ==0:\n",
    "                return grid[i][j]\n",
    "            if save[i][j]>=0:\n",
    "                return save[i][j]\n",
    "            if i==0 and j>0:\n",
    "                pathsum = dfs(i,j-1) + grid[i][j]\n",
    "            if j==0 and i>0:\n",
    "                pathsum = dfs(i-1,j) + grid[i][j]\n",
    "            if i>0 and j>0:\n",
    "                pathsum = min(dfs(i,j-1),dfs(i-1,j))+grid[i][j]\n",
    "            save[i][j] = pathsum\n",
    "            return pathsum\n",
    "        return dfs(m-1,n-1)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.memo = []\n",
    "\n",
    "    def minPathSum(self, grid: List[List[int]]) -> int:\n",
    "        self.memo = [[-1] * len(grid[0]) for _ in range(len(grid))]\n",
    "        return self.dp(grid, 0, 0)\n",
    "\n",
    "    def dp(self, grid, row, col):\n",
    "        if row == (len(grid) - 1) and col == (len(grid[0]) - 1):\n",
    "            self.memo[row][col] = grid[row][col]\n",
    "            return self.memo[row][col]\n",
    "        if row >= len(grid) or col >= len(grid[0]):\n",
    "            return float('inf')\n",
    "\n",
    "        if self.memo[row][col] != -1:\n",
    "            return self.memo[row][col]\n",
    "\n",
    "        self.memo[row][col] = min(\n",
    "            self.dp(grid, row + 1, col),\n",
    "            self.dp(grid, row, col + 1)\n",
    "        ) + grid[row][col]\n",
    "\n",
    "        return self.memo[row][col]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minPathSum(self, grid: List[List[int]]) -> int:\n",
    "        #递归法+备忘录\n",
    "        #定义dp[i][j]为从[0][0]到[i][j]的数字总和。\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        memo = [[99999] * n for i in range(m)]\n",
    "        def dp(grid,i,j):\n",
    "            if i == 0 and j == 0:\n",
    "                return grid[0][0]\n",
    "            if i < 0 or j < 0:\n",
    "                return float('inf')\n",
    "            if memo[i][j] != 99999:\n",
    "                return memo[i][j]\n",
    "            memo[i][j] = min(dp(grid,i-1,j),dp(grid,i,j-1)) + grid[i][j]\n",
    "            return memo[i][j]\n",
    "        return dp(grid,m-1,n-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 这是一道经典的动态规划问题，可以使用动态规划算法来解决。我们可以定义一个二维数组 dp，其中 dp[i][j] 表示从左上角到 (i, j) 的最小路径和。根据题目要求，我们只能向右或向下移动，因此在计算 dp[i][j] 时，只需要考虑 dp[i-1][j] 和 dp[i][j-1] 两个状态的值，取其中较小的一个加上 grid[i][j] 即可。\n",
    "\n",
    "def f(grid):\n",
    "    dp = []\n",
    "    row = len(grid)\n",
    "    col = len(grid[0])\n",
    "    maxV = grid[0][0]\n",
    "    for x in grid:\n",
    "        for y in x:\n",
    "            maxV = max(maxV, y)\n",
    "\n",
    "    maxV += 1 \n",
    "\n",
    "\n",
    "    for i in range(row):\n",
    "        dp.append([])\n",
    "        temp = dp[-1]\n",
    "        for j in range(col):\n",
    "            temp.append(maxV)\n",
    "            \n",
    "    print('dp\\n', dp)\n",
    "    dp[0][0] = grid[0][0]\n",
    "\n",
    "    for i in range(row):\n",
    "        for j in range(col):\n",
    "            if i == 0 and j == 0:\n",
    "                continue \n",
    "            \n",
    "            if i == 0:\n",
    "                dp[i][j] = dp[i][j-1] + grid[i][j]\n",
    "                continue \n",
    "            if j == 0:\n",
    "                dp[i][j] = dp[i-1][j] + grid[i][j]\n",
    "                continue\n",
    "\n",
    "            dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]\n",
    "\n",
    "    return dp[row-1][col-1]\n",
    "\n",
    "class Solution:\n",
    "    def minPathSum(self, grid: List[List[int]]) -> int:\n",
    "        return f(grid)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minPathSum(self, grid: List[List[int]]) -> int:\n",
    "\n",
    "        m,n = len(grid),len(grid[0])\n",
    "        save = [[-1 for j in range(n)]for i in range(m)]\n",
    "        def dfs(i,j): \n",
    "            if i == 0 and j == 0:\n",
    "                return grid[i][j]\n",
    "            if save[i][j]>=0:\n",
    "                return save[i][j]\n",
    "            if i==0 and j>0:\n",
    "                pathsum = dfs(i,j-1)+grid[i][j]\n",
    "            if j==0 and i>0:\n",
    "                pathsum =dfs(i-1,j)+grid[i][j]\n",
    "            elif i>0 and j >0:\n",
    "                pathsum = min(dfs(i-1,j), dfs(i,j-1))+grid[i][j]\n",
    "            save[i][j] =  pathsum\n",
    "            return pathsum\n",
    "        return dfs(m-1,n-1) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "import heapq\n",
    "\n",
    "\n",
    "class Node(object):\n",
    "    def __init__(self, x, y, val):\n",
    "        self.x = x\n",
    "        self.y = y\n",
    "        self.val = val\n",
    "\n",
    "    def __lt__(self, other):\n",
    "        return self.val < other.val\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minPathSum(self, grid: List[List[int]]) -> int:\n",
    "        if len(grid) == 0:\n",
    "            return 0\n",
    "        n = len(grid)\n",
    "        m = len(grid[0])\n",
    "        q = [Node(0, 0, grid[0][0])]\n",
    "        visited = [[False for _ in range(m)] for _ in range(n)]\n",
    "        while len(q) != 0:\n",
    "            cur_node = heapq.heappop(q)\n",
    "            if visited[cur_node.x][cur_node.y]:\n",
    "                continue\n",
    "            visited[cur_node.x][cur_node.y] = True\n",
    "            if cur_node.x == (n - 1) and cur_node.y == (m - 1):\n",
    "                return cur_node.val\n",
    "            for dx, dy in zip([1, 0], [0, 1]):\n",
    "                next_x = cur_node.x + dx\n",
    "                next_y = cur_node.y + dy\n",
    "                if 0 <= next_x < n and 0 <= next_y < m and not visited[next_x][next_y]:\n",
    "                    next_node = Node(next_x, next_y, cur_node.val + grid[next_x][next_y])\n",
    "                    heapq.heappush(q, next_node)\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minPathSum(self, grid: List[List[int]]) -> int:\n",
    "        m,n =len(grid),len(grid[0])\n",
    "        save = [[-1]*n for i in range(m)]\n",
    "        def dfs(i,j):\n",
    "            if i==0 and j ==0:\n",
    "                return grid[i][j]\n",
    "            if save[i][j]>=0:\n",
    "                return save[i][j]\n",
    "            if i==0 and j>0:\n",
    "                pathsum = dfs(i,j-1) + grid[i][j]\n",
    "            if j==0 and i>0:\n",
    "                pathsum = dfs(i-1,j) + grid[i][j]\n",
    "            if i>0 and j>0:\n",
    "                pathsum = min(dfs(i,j-1),dfs(i-1,j))+grid[i][j]\n",
    "            save[i][j] = pathsum\n",
    "            return pathsum\n",
    "        return dfs(m-1,n-1)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.memo = None\n",
    "\n",
    "    def minPathSum(self, grid: List[List[int]]) -> int:\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        # 构造备忘录，初始值全部设为 -1\n",
    "        self.memo = [[-1 for _ in range(n)] for _ in range(m)]\n",
    "\n",
    "        return self.dp(grid, m - 1, n - 1)\n",
    "\n",
    "    def dp(self, grid: List[List[int]], i: int, j: int) -> int:\n",
    "        # base case\n",
    "        if i == 0 and j == 0:\n",
    "            return grid[0][0]\n",
    "        if i < 0 or j < 0:\n",
    "            return float('inf')\n",
    "        # 避免重复计算\n",
    "        if self.memo[i][j] != -1:\n",
    "            return self.memo[i][j]\n",
    "        # 将计算结果记入备忘录\n",
    "        self.memo[i][j] = min(\n",
    "            self.dp(grid, i - 1, j),\n",
    "            self.dp(grid, i, j - 1)\n",
    "        ) + grid[i][j]\n",
    "\n",
    "        return self.memo[i][j]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minPathSum(self, grid: List[List[int]]) -> int:\n",
    "\n",
    "        m,n = len(grid),len(grid[0])\n",
    "        save = [[-1 for j in range(n)]for i in range(m)]\n",
    "        def dfs(i,j): \n",
    "            if i == 0 and j == 0:\n",
    "                return grid[i][j]\n",
    "            if save[i][j]>=0:\n",
    "                return save[i][j]\n",
    "            if i==0 and j>0:\n",
    "                pathsum = dfs(i,j-1)+grid[i][j]\n",
    "            if j==0 and i>0:\n",
    "                pathsum =dfs(i-1,j)+grid[i][j]\n",
    "            elif i>0 and j >0:\n",
    "                pathsum = min(dfs(i-1,j), dfs(i,j-1))+grid[i][j]\n",
    "            save[i][j] =  pathsum\n",
    "            return pathsum\n",
    "        return dfs(m-1,n-1) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minPathSum(self, grid: List[List[int]]) -> int:\n",
    "\n",
    "        m,n = len(grid),len(grid[0])\n",
    "        save = [[-1 for j in range(n)]for i in range(m)]\n",
    "        def dfs(i,j): \n",
    "            if i == 0 and j == 0:\n",
    "                return grid[i][j]\n",
    "            if save[i][j]>=0:\n",
    "                return save[i][j]\n",
    "            if i==0 and j>0:\n",
    "                pathsum = dfs(i,j-1)+grid[i][j]\n",
    "            if j==0 and i>0:\n",
    "                pathsum =dfs(i-1,j)+grid[i][j]\n",
    "            if i>0 and j >0:\n",
    "                pathsum = min(dfs(i-1,j), dfs(i,j-1))+grid[i][j]\n",
    "            save[i][j] =  pathsum\n",
    "            return pathsum\n",
    "        return dfs(m-1,n-1) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minPathSum(self, grid: List[List[int]]) -> int:\n",
    "        if not grid:\n",
    "            return 0\n",
    "        n = len(grid)\n",
    "        m = len(grid[0])\n",
    "\n",
    "        for i in range(0, n):\n",
    "            for j in range(0, m):\n",
    "                if i == 0 and j == 0:\n",
    "                    continue\n",
    "                elif i == 0:\n",
    "                    grid[i][j] = grid[i][j - 1] + grid[i][j]\n",
    "                elif j == 0:\n",
    "                    grid[i][j] = grid[i - 1][j] + grid[i][j]\n",
    "                else:\n",
    "                    grid[i][j] = min(grid[i - 1][j], grid[i][j - 1]) + grid[i][j]\n",
    "        return grid[-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minPathSum(self, grid: List[List[int]]) -> int:\n",
    "        lenx = len(grid)\n",
    "        leny = len(grid[0])\n",
    "        dp = [[15000] * leny for _ in range(lenx)]\n",
    "        dp[0][0] = grid[0][0]\n",
    "        for i in range(lenx):\n",
    "            for j in range(leny):\n",
    "                if i - 1 >= 0 and j-1 >= 0:\n",
    "                    dp[i][j] = min(dp[i-1][j],dp[i][j-1]) + grid[i][j]\n",
    "                    continue\n",
    "                if j - 1 >= 0 and i == 0:\n",
    "                    dp[i][j] = min(dp[i][j-1],dp[i][j]) + grid[i][j]\n",
    "                    continue\n",
    "                if j == 0 and i-1>=0 :\n",
    "                    dp[i][j] = min(dp[i][j],dp[i-1][j]) + grid[i][j]\n",
    "        print(dp)\n",
    "        return dp[lenx-1][leny-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minPathSum(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        # 预处理操作\n",
    "        for i in range(1,m):\n",
    "            grid[i][0] += grid[i-1][0]\n",
    "        for i in range(1,n):\n",
    "            grid[0][i] += grid[0][i-1]\n",
    "        for i in range(1,m):\n",
    "            for j in range(1,n):\n",
    "                grid[i][j] = grid[i][j] + min(grid[i-1][j],grid[i][j-1])\n",
    "        return grid[m-1][n-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minPathSum(self, grid: List[List[int]]) -> int:\n",
    "        if not grid: return \n",
    "        m,n = len(grid), len(grid[0])\n",
    "        for i in range(1,m):\n",
    "            grid[i][0]+=grid[i-1][0]\n",
    "        for i in range(1,n):\n",
    "            grid[0][i]+=grid[0][i-1]\n",
    "        for i in range(1,m):\n",
    "            for j in range(1,n):\n",
    "                grid[i][j]+=min(grid[i-1][j],grid[i][j-1])\n",
    "        return grid[-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minPathSum(self, grid: List[List[int]]) -> int:\n",
    "        r, d = len(grid), len(grid[0]) \n",
    "        for i in range(len(grid)):\n",
    "            for j in range(0,len(grid[0])):\n",
    "                if i == 0 and j == 0:\n",
    "                    grid[0][0] == grid[0][0]\n",
    "                elif i == 0:\n",
    "                    grid[0][j] += grid[0][j-1]\n",
    "                elif j == 0:\n",
    "                    grid[i][0] += grid[i-1][0]\n",
    "                else:\n",
    "                    grid[i][j] += min(grid[i-1][j],grid[i][j-1])\n",
    "        return grid[r-1][d-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minPathSum(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        # 预处理操作\n",
    "        for i in range(1,m):\n",
    "            grid[i][0] += grid[i-1][0]\n",
    "        for i in range(1,n):\n",
    "            grid[0][i] += grid[0][i-1]\n",
    "        for i in range(1,m):\n",
    "            for j in range(1,n):\n",
    "                grid[i][j] = grid[i][j] + min(grid[i-1][j],grid[i][j-1])\n",
    "        return grid[m-1][n-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minPathSum(self, grid: List[List[int]]) -> int:\n",
    "        m,n=len(grid),len(grid[0])\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if i==0 and j==0:continue\n",
    "                elif i==0:grid[i][j]+=grid[i][j-1]\n",
    "                elif j==0:grid[i][j]+=grid[i-1][j]\n",
    "                else:grid[i][j]+=min(grid[i-1][j],grid[i][j-1])\n",
    "        return grid[-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minPathSum(self, grid: List[List[int]]) -> int:\n",
    "       # dp[i][j] = min(dp[i-1][j],dp[i][j-1])+dp[i][j]\n",
    "        m,n = len(grid),len(grid[0])\n",
    "        for i in range(m):\n",
    "           for j in range(n):\n",
    "               if i ==0 and j ==0:\n",
    "                    continue\n",
    "               if i ==0:\n",
    "                grid[i][j] = grid[i][j-1]+grid[i][j]\n",
    "               elif j ==0:\n",
    "                grid[i][j] =grid[i-1][j]+grid[i][j]\n",
    "               else:\n",
    "                   grid[i][j] = min(grid[i-1][j],grid[i][j-1])+grid[i][j]\n",
    "        return grid[m-1][n-1]\n",
    "\n",
    "                  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minPathSum(self, grid: List[List[int]]) -> int:\n",
    "\n",
    "\n",
    "       # dp[i][j] = min(dp[i-1][j],dp[i][j-1])+dp[i][j]\n",
    "        m,n = len(grid),len(grid[0])\n",
    "        for j in range(1,n):\n",
    "            grid[0][j] = grid[0][j-1]+grid[0][j]\n",
    "        for i in range(1,m):\n",
    "            grid[i][0] =grid[i-1][0] + grid[i][0]   \n",
    "        for i in range(1,m):\n",
    "           for j in range(1,n):\n",
    "               grid[i][j] = min(grid[i-1][j],grid[i][j-1])+grid[i][j]\n",
    "        return grid[m-1][n-1]\n",
    "\n",
    "                  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minPathSum(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        # 预处理操作\n",
    "        for i in range(1,m):\n",
    "            grid[i][0] += grid[i-1][0]\n",
    "        for i in range(1,n):\n",
    "            grid[0][i] += grid[0][i-1]\n",
    "        for i in range(1,m):\n",
    "            for j in range(1,n):\n",
    "                grid[i][j] = grid[i][j] + min(grid[i-1][j],grid[i][j-1])\n",
    "        return grid[m-1][n-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minPathSum(self, grid: List[List[int]]) -> int:\n",
    "       # dp[i][j] = min(dp[i-1][j],dp[i][j-1])+dp[i][j]\n",
    "        m,n = len(grid),len(grid[0])\n",
    "        for i in range(m):\n",
    "           for j in range(n):\n",
    "               if i ==0 and j ==0:\n",
    "                    continue\n",
    "               if i ==0:\n",
    "                grid[i][j] = grid[i][j-1]+grid[i][j]\n",
    "               elif j ==0:grid[i][j] =grid[i-1][j]+grid[i][j]\n",
    "               else:\n",
    "                   grid[i][j] = min(grid[i-1][j],grid[i][j-1])+grid[i][j]\n",
    "        return grid[m-1][n-1]\n",
    "\n",
    "                  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minPathSum(self, grid: List[List[int]]) -> int:\n",
    "\n",
    "\n",
    "       # dp[i][j] = min(dp[i-1][j],dp[i][j-1])+dp[i][j]\n",
    "        m,n = len(grid),len(grid[0])\n",
    "        for j in range(1,n):\n",
    "            grid[0][j] = grid[0][j-1]+grid[0][j]\n",
    "        for i in range(1,m):\n",
    "            grid[i][0] =grid[i-1][0] + grid[i][0]   \n",
    "        for i in range(1,m):\n",
    "           for j in range(1,n):\n",
    "               grid[i][j] = min(grid[i-1][j],grid[i][j-1])+grid[i][j]\n",
    "        return grid[m-1][n-1]\n",
    "\n",
    "                  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minPathSum(self, grid: List[List[int]]) -> int:\n",
    "\n",
    "\n",
    "       # dp[i][j] = min(dp[i-1][j],dp[i][j-1])+dp[i][j]\n",
    "        m,n = len(grid),len(grid[0])\n",
    "        for j in range(1,n):\n",
    "            grid[0][j] = grid[0][j-1]+grid[0][j]\n",
    "        for i in range(1,m):\n",
    "            grid[i][0] =grid[i-1][0] + grid[i][0]   \n",
    "        for i in range(1,m):\n",
    "           for j in range(1,n):\n",
    "               grid[i][j] = min(grid[i-1][j],grid[i][j-1])+grid[i][j]\n",
    "        return grid[m-1][n-1]\n",
    "\n",
    "                  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minPathSum(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        # 预处理操作\n",
    "        for i in range(1,m):\n",
    "            grid[i][0] += grid[i-1][0]\n",
    "        for i in range(1,n):\n",
    "            grid[0][i] += grid[0][i-1]\n",
    "        for i in range(1,m):\n",
    "            for j in range(1,n):\n",
    "                grid[i][j] = grid[i][j] + min(grid[i-1][j],grid[i][j-1])\n",
    "        return grid[m-1][n-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minPathSum(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        dp = [[0] * n for _ in range(m)]\n",
    "        dp[0][0] = grid[0][0]\n",
    "        for i in range(1, m):\n",
    "            dp[i][0] = grid[i][0] + dp[i - 1][0]\n",
    "        for j in range(1, n):\n",
    "            dp[0][j] = grid[0][j] + dp[0][j - 1]\n",
    "        for i in range(1, m):\n",
    "            for j in range(1, n):\n",
    "                dp[i][j] = grid[i][j] + min(dp[i - 1][j], dp[i][j - 1])\n",
    "        return dp[-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minPathSum(self, grid: List[List[int]]) -> int:\n",
    "        m,n=len(grid),len(grid[0])\n",
    "        dp=[[0]*n for i in range(m)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if i==0 and j==0:\n",
    "                    dp[i][j]=grid[i][j]\n",
    "                elif i==0:\n",
    "                    dp[i][j]=dp[i][j-1]+grid[i][j]\n",
    "                elif j==0:\n",
    "                    dp[i][j]=dp[i-1][j]+grid[i][j]\n",
    "                else:\n",
    "                    dp[i][j]=min(dp[i-1][j],dp[i][j-1])+grid[i][j]\n",
    "        return dp[-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minPathSum(self, grid: List[List[int]]) -> int:\n",
    "        n = len(grid)\n",
    "        m = len(grid[0])\n",
    "        dp = [[0 for i in range(m)] for j in range(n)]\n",
    "        dp[0][0] = grid[0][0]\n",
    "        for i in range(1, m):\n",
    "            dp[0][i] = dp[0][i - 1] + grid[0][i]\n",
    "        for j in range(1, n):\n",
    "            dp[j][0] = dp[j - 1][0] + grid[j][0]\n",
    "        for i in range(1, n):\n",
    "            for j in range(1, m):\n",
    "                dp[i][j] = min(dp[i-1][j], dp[i][j - 1]) + grid[i][j]\n",
    "        return dp[-1][-1]\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minPathSum(self, grid: List[List[int]]) -> int:\n",
    "        pq = []\n",
    "        pq.append((0,0,0))\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        dist = [[-1 for i in range(n)] for j in range(m)]\n",
    "        while len(pq) > 0:\n",
    "            d,i,j = heapq.heappop(pq)\n",
    "            if dist[i][j] != -1:\n",
    "                continue\n",
    "            dist[i][j] = d\n",
    "            if i < m-1:\n",
    "                heapq.heappush(pq, (d+grid[i][j], i+1, j))\n",
    "            if j < n-1:\n",
    "                heapq.heappush(pq, (d+grid[i][j], i, j+1))\n",
    "        return dist[m-1][n-1]+grid[m-1][n-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minPathSum(self, grid: List[List[int]]) -> int:\n",
    "        if not grid or not grid[0]:\n",
    "            return 0\n",
    "        \n",
    "        rows, columns = len(grid), len(grid[0])\n",
    "        dp = [[0] * columns for _ in range(rows)]\n",
    "        dp[0][0] = grid[0][0]\n",
    "        for i in range(1, rows):\n",
    "            dp[i][0] = dp[i - 1][0] + grid[i][0]\n",
    "        for j in range(1, columns):\n",
    "            dp[0][j] = dp[0][j - 1] + grid[0][j]\n",
    "        for i in range(1, rows):\n",
    "            for j in range(1, columns):\n",
    "                dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j]\n",
    "        \n",
    "        return dp[rows - 1][columns - 1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minPathSum(self, grid: List[List[int]]) -> int:\n",
    "        dp = [[2 ** 31] * (len(grid[0]) + 1)]\n",
    "        for i in range(len(grid)):\n",
    "            dp.append([2 ** 31] + grid[i])\n",
    "        dp[1][0] = 0\n",
    "        for y in range(1, len(dp)):\n",
    "            for x in range(1, len(dp[0])):\n",
    "                dp[y][x] = min(dp[y][x - 1] + dp[y][x], dp[y - 1][x] + dp[y][x])\n",
    "        return dp[-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minPathSum(self, grid: List[List[int]]) -> int:        \n",
    "        m, n = len(grid), len(grid[0])\n",
    "        if m == n == 1: return grid[0][0]\n",
    "        dp = [[0]*n for _ in range(m)]\n",
    "        dp[0][0] = grid[0][0]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if i == 0: dp[0][j] = dp[0][j-1] + grid[0][j]\n",
    "                elif j == 0: dp[i][0] = dp[i-1][0] + grid[i][0]\n",
    "                else: dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1])\n",
    "        return dp[m-1][n-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minPathSum(self, grid: List[List[int]]) -> int:\n",
    "        dp = [[0] * len(grid[0]) for _ in range(len(grid))]\n",
    "\n",
    "        dp[0][0] = grid[0][0]\n",
    "\n",
    "        for i in range(1, len(dp)):\n",
    "            dp[i][0] = dp[i - 1][0] + grid[i][0]\n",
    "\n",
    "        for j in range(1, len(dp[0])):\n",
    "            dp[0][j] = dp[0][j - 1] + grid[0][j]\n",
    "\n",
    "        for i in range(1, len(grid)):\n",
    "            for j in range(1, len(grid[0])):\n",
    "                dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j]\n",
    "        return dp[len(grid) - 1][len(grid[0]) - 1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minPathSum(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "\n",
    "        min_path = [[-1] * n for _ in range(m)]\n",
    "        min_path[0][0] = grid[0][0]\n",
    "\n",
    "        for i in range(1, n):\n",
    "            min_path[0][i] = min_path[0][i - 1] + grid[0][i]\n",
    "\n",
    "        for j in range(1, m):\n",
    "            min_path[j][0] = min_path[j - 1][0] + grid[j][0]\n",
    "\n",
    "        for i in range(1, m):\n",
    "            for j in range(1, n):\n",
    "                min_path[i][j] = min(min_path[i - 1][j], min_path[i][j - 1]) + grid[i][j]\n",
    "        return min_path[m - 1][n - 1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minPathSum(self, grid: List[List[int]]) -> int:\n",
    "        m=len(grid)  # 行\n",
    "        n=len(grid[0])  # 列\n",
    "        dp=[[0]*n for _ in range(m)]\n",
    "        dp[0][0]=grid[0][0]\n",
    "        if n>1:\n",
    "            for j in range(1,n):\n",
    "                dp[0][j]=dp[0][j-1]+grid[0][j]\n",
    "        if m>1:\n",
    "            for i in range(1,m):\n",
    "                dp[i][0]=dp[i-1][0]+grid[i][0]\n",
    "        for i in range(1,m):\n",
    "            for j in range(1,n):\n",
    "                dp[i][j]=min(dp[i-1][j],dp[i][j-1])+grid[i][j]\n",
    "        return dp[m-1][n-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minPathSum(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "\n",
    "        min_path = [[-1] * n for _ in range(m)]\n",
    "        min_path[0][0] = grid[0][0]\n",
    "\n",
    "        for i in range(1, n):\n",
    "            min_path[0][i] = min_path[0][i - 1] + grid[0][i]\n",
    "\n",
    "        for j in range(1, m):\n",
    "            min_path[j][0] = min_path[j - 1][0] + grid[j][0]\n",
    "\n",
    "        for i in range(1, m):\n",
    "            for j in range(1, n):\n",
    "                min_path[i][j] = min(min_path[i - 1][j], min_path[i][j - 1]) + grid[i][j]\n",
    "        return min_path[m - 1][n - 1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minPathSum(self, grid: List[List[int]]) -> int:\n",
    "        if len(grid) == 0: return 0\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        dp = [[0]*n for _ in range(m)]\n",
    "        dp[0][0] = grid[0][0]\n",
    "        for i in range(1, m):\n",
    "            dp[i][0] = dp[i-1][0] + grid[i][0]\n",
    "        for j in range(1, n):\n",
    "            dp[0][j] = dp[0][j-1] + grid[0][j]\n",
    "        for i in range(1, m):\n",
    "            for j in range(1, n):\n",
    "                dp[i][j] = min(dp[i-1][j]+grid[i][j], dp[i][j-1]+grid[i][j])\n",
    "        return dp[-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minPathSum(self, grid: list[list[int]]) -> int:\n",
    "        m=len(grid)  # 行\n",
    "        n=len(grid[0])  # 列\n",
    "        dp=[[0]*n for _ in range(m)]\n",
    "        dp[0][0]=grid[0][0]\n",
    "        if n>1:\n",
    "            for j in range(1,n):\n",
    "                dp[0][j]=dp[0][j-1]+grid[0][j]\n",
    "        if m>1:\n",
    "            for i in range(1,m):\n",
    "                dp[i][0]=dp[i-1][0]+grid[i][0]\n",
    "        for i in range(1,m):\n",
    "            for j in range(1,n):\n",
    "                dp[i][j]=min(dp[i-1][j],dp[i][j-1])+grid[i][j]\n",
    "        return dp[m-1][n-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minPathSum(self, grid: List[List[int]]) -> int:\n",
    "        dp = [[2 ** 31] * (len(grid[0]) + 1)]\n",
    "        for i in range(len(grid)):\n",
    "            dp.append([2 ** 31] + grid[i])\n",
    "        dp[1][0] = 0\n",
    "        for y in range(1, len(dp)):\n",
    "            for x in range(1, len(dp[0])):\n",
    "                dp[y][x] = min(dp[y][x - 1] + dp[y][x], dp[y - 1][x] + dp[y][x])\n",
    "        return dp[-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minPathSum(self, grid: List[List[int]]) -> int:\n",
    "        if not grid or not grid[0]:\n",
    "            return 0\n",
    "        \n",
    "        rows=len(grid)\n",
    "        colums=len(grid[0])\n",
    "        dp=[[0]*colums for i in range(rows)]\n",
    "\n",
    "        dp[0][0]=grid[0][0]\n",
    "\n",
    "        for i in range(1,rows):\n",
    "            dp[i][0]=dp[i-1][0]+grid[i][0]\n",
    "\n",
    "        for i in range(1,colums):\n",
    "            dp[0][i]=dp[0][i-1]+grid[0][i]\n",
    "\n",
    "        for i in range(1,rows):\n",
    "            for j in range(1,colums):\n",
    "                min_cost=min(dp[i][j-1],dp[i-1][j])\n",
    "                dp[i][j]=grid[i][j]+min_cost\n",
    "        \n",
    "       \n",
    "        print('*'*10)\n",
    "        for row in dp:\n",
    "            print(row)\n",
    "\n",
    "        return dp[-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minPathSum(self, grid: List[List[int]]) -> int:\n",
    "        n,m = len(grid),len(grid[0])\n",
    "        dp = [[-1]*m for _ in range(n)]\n",
    "        def f(grid,i,j):\n",
    "            if dp[i][j] != -1:\n",
    "                return dp[i][j]\n",
    "            if i==0 and j==0:\n",
    "                return grid[i][j]\n",
    "            up = float('inf')\n",
    "            left = float('inf')\n",
    "            if i-1>=0:\n",
    "                up = f(grid,i-1,j)\n",
    "            if j-1>=0:\n",
    "                left = f(grid,i,j-1)\n",
    "            ans = min(up,left)+grid[i][j]\n",
    "            dp[i][j] = ans\n",
    "            return ans\n",
    "        return f(grid,len(grid)-1,len(grid[0])-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# https://labuladong.github.io/algo/di-er-zhan-a01c6/yong-dong--63ceb/dong-tai-g-52f34/\n",
    "# 一般来说，让你在二维矩阵中求最优化问题（最大值或者最小值），肯定需要递归 + 备忘录，也就是动态规划技巧。\n",
    "\n",
    "# 这个框架懂，但是最后return那里不太懂，不太懂的原因是因为：又想不通递归逻辑了。我的脑袋能压几个栈呀，框架懂就行了就容易背了\n",
    "\n",
    "# 方法一：动规。备忘录方法。自顶向下\n",
    "class Solution:\n",
    "    def minPathSum(self, grid: List[List[int]]) -> int:\n",
    "        def dp(grid, i, j):\n",
    "            # base case 1\n",
    "            if i == 0 and j == 0:\n",
    "                return grid[0][0]\n",
    "            \n",
    "            # base case 2\n",
    "            # 返回一个很大的值，这样取min的时候就不会取到了\n",
    "            if i < 0 or j < 0:\n",
    "                return float(\"inf\")\n",
    "\n",
    "            # 消除重叠子问题\n",
    "            if memo[i][j] != -1:\n",
    "                return memo[i][j]\n",
    "\n",
    "            # 状态转移,# 将计算结果记入备忘录\n",
    "            # 看文章解释就知道这句啥意思了\n",
    "            memo[i][j] = min(\n",
    "                dp(grid, i-1, j),\n",
    "                dp(grid, i, j-1)\n",
    "            ) + grid[i][j]\n",
    "\n",
    "            return memo[i][j]\n",
    "\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        # 构造备忘录，初始值全部设为 -1\n",
    "        memo = [[-1] * n for _ in range(m)]\n",
    "        return dp(grid, m-1, n-1)\n",
    "\n",
    "\n",
    "# 方法二：标准动规。自底向上\n",
    "# class Solution:\n",
    "#     def minPathSum(self, grid: List[List[int]]) -> int:\n",
    "#         m, n = len(grid), len(grid[0])\n",
    "#         # 构造备忘录，初始值全部设为 -1\n",
    "#         dp = [[-1] * n for _ in range(m)]\n",
    "        \n",
    "#         dp[0][0] = grid[0][0]\n",
    "\n",
    "#         # 边界值处理\n",
    "#         for i in range(1, m):\n",
    "#             dp[i][0] = dp[i-1][0] + grid[i][0]\n",
    "#         for j in range(1, n):\n",
    "#             dp[0][j] = dp[0][j-1] + grid[0][j]\n",
    "\n",
    "#         # 状态转移\n",
    "#         for i in range(1, m):\n",
    "#             for j in range(1, n):\n",
    "#                 dp[i][j] = min(\n",
    "#                     dp[i-1][j], dp[i][j-1]\n",
    "#                 ) + grid[i][j]\n",
    "        \n",
    "#         return dp[m-1][n-1]\n",
    "        \n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minPathSum(self, grid: List[List[int]]) -> int:\n",
    "\n",
    "        # 这是一个图的遍历问题\n",
    "        # 我们知道了一个完全连接图\n",
    "        # 节点数字有n_nods = len(grid)\n",
    "        # 如果当前要求节点i到节点j的最短路径，\n",
    "        # 用min_distances来存储当前从左上角到其余各个节点的最短路径\n",
    "        # min_distances[j] = min([min_distances[j], min_distances[i]+grid[i][j]])\n",
    "        # 我们需要用一个数组来用BFS遍历所有路径并更新min_distances\n",
    "        \n",
    "        cur_queue = []\n",
    "        cur_queue.append((0,0))\n",
    "        min_distances = [[float(\"inf\") for j in range(len(grid[0]))] for i in range(len(grid))]\n",
    "        min_distances[0][0] = grid[0][0]\n",
    "        cur_queue = set([(0, 1), (1, 0)])\n",
    "        next_queue = set()\n",
    "        while len(cur_queue) > 0:\n",
    "            for row_id, col_id in cur_queue:\n",
    "                if row_id < len(grid) and col_id < len(grid[0]):\n",
    "                    tmp = min_distances[row_id][col_id]\n",
    "                    if row_id - 1 >= 0:\n",
    "                        tmp = min([min_distances[row_id-1][col_id] + grid[row_id][col_id], \n",
    "                                                                        tmp])  \n",
    "                    if col_id - 1 >= 0:\n",
    "                        tmp = min([min_distances[row_id][col_id-1] + grid[row_id][col_id], \n",
    "                                                                        tmp])   \n",
    "                    min_distances[row_id][col_id] = tmp\n",
    "                    next_queue.add((row_id+1, col_id))\n",
    "                    next_queue.add((row_id, col_id+1))\n",
    "            # print(min_distances)\n",
    "            cur_queue = {item for item in next_queue}\n",
    "            next_queue = set()\n",
    "            # break\n",
    "\n",
    "        return min_distances[-1][-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minPathSum(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        self.memo = [[-1]*n for _ in range(m)]\n",
    "        return self.dp(grid, m-1, n-1)\n",
    "    def dp(self, grid, i, j):\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        if i == 0 and j == 0:\n",
    "            return grid[0][0]\n",
    "        if i < 0 or j < 0:\n",
    "            return float('inf')\n",
    "        if self.memo[i][j] != -1:\n",
    "            return self.memo[i][j]\n",
    "        self.memo[i][j] = min(\n",
    "            self.dp(grid, i-1, j),\n",
    "            self.dp(grid, i, j-1)\n",
    "        ) + grid[i][j]\n",
    "        return self.memo[i][j]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minPathSum(self, grid: List[List[int]]) -> int:\n",
    "        n = len(grid)\n",
    "        m = len(grid[0])\n",
    "        dp = [[0] * m for i in range(n)]\n",
    "        print(dp)\n",
    "        dp[0][0] = grid[0][0]\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                if i == 0 and j == 0:\n",
    "                    continue\n",
    "                if i == 0:\n",
    "                    dp[i][j] = dp[i][j-1] + grid[i][j]\n",
    "                elif j == 0:\n",
    "                    dp[i][j] = dp[i-1][j] + grid[i][j]\n",
    "                else:\n",
    "                    dp[i][j] = min(dp[i-1][j],dp[i][j-1]) + grid[i][j]\n",
    "        return dp[-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minPathSum(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "\n",
    "        min_path = [[-1] * n for _ in range(m)]\n",
    "        min_path[0][0] = grid[0][0]\n",
    "\n",
    "        return self.sum_path(grid, min_path, m - 1, n - 1)\n",
    "\n",
    "    def sum_path(self, grid, min_path, m, n):\n",
    "        if m < 0 or n < 0:\n",
    "            return 9999\n",
    "        elif min_path[m][n] >= 0:\n",
    "            return min_path[m][n]\n",
    "        min_path[m][n] = (\n",
    "            min(self.sum_path(grid, min_path, m - 1, n), self.sum_path(grid, min_path, m, n - 1)) + grid[m][n]\n",
    "        )\n",
    "        return min_path[m][n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minPathSum(self, grid: List[List[int]]) -> int:\n",
    "        print(grid)\n",
    "        from itertools import accumulate\n",
    "        grid[0] = list(accumulate(grid[0]))\n",
    "        first_column = list(accumulate(list(zip(*grid))[0]))\n",
    "        for i in range(len(grid)):\n",
    "            grid[i][0] = first_column[i]\n",
    "        print(grid)\n",
    "        for i in range(1, len(grid)):\n",
    "            for j in range(1, len(grid[0])):\n",
    "                print(i, j, grid[i][j], )\n",
    "                grid[i][j] = min(grid[i-1][j], grid[i][j-1]) + grid[i][j]\n",
    "        print(grid)\n",
    "        return grid[-1][-1]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minPathSum(self, grid: List[List[int]]) -> int:\n",
    "\n",
    "        n, m = len(grid), len(grid[0])\n",
    "\n",
    "        dp = [[0 for _ in range(m)] for _ in range(n)]\n",
    "\n",
    "\n",
    "        dp[0][0] = grid[0][0]\n",
    "        for i in range(1, n):\n",
    "            dp[i][0] = dp[i-1][0] + grid[i][0]\n",
    "        \n",
    "        for j in range(1, m):\n",
    "            dp[0][j] = dp[0][j-1] + grid[0][j]\n",
    "\n",
    "        for i in range(1, n):\n",
    "            for j in range(1, m):\n",
    "\n",
    "                dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]\n",
    "\n",
    "        print(dp)\n",
    "        return dp[n-1][m-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minPathSum(self, grid) -> int:\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        dp = [[0 for i in range(n)] for j in range(m)]\n",
    "        if n <= 1 or m <= 1:\n",
    "            return sum(grid[0])\n",
    "        dp[0][0] = grid[0][0]\n",
    "        for i in range(1,m):\n",
    "            dp[i][0] += dp[i-1][0] + grid[i][0]\n",
    "        for j in range(1,n):\n",
    "            dp[0][j] += dp[0][j-1]+ grid[0][j]\n",
    "        print(dp)\n",
    "        for i in range(1, m):\n",
    "            for j in range(1, n):\n",
    "                dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j]\n",
    "        print(dp)\n",
    "        return dp[-1][-1]"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
